package edu.iastate.cs228.hw2;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 
 * @author Devon Eilers
 * 
 */
public class Ranking implements IRanking 
{
	
	/**
	 * HashMap containing a rank
	 */
	private HashMap<Integer,Integer> ranks;
	
	/**
	 * This is useful when finding the corresponding rank order for sigma 2 when the rankings for sigma 1 have been sorted
	 */
	private HashMap<Integer,Integer> ranksOpposite;
	
	/**
	 * The number of inversions for this Ranking
	 */
	private int inversionCount;
	
	/**
	 * Constructs a random ranking of the numbers 1 through n. Throws an
	 * IllegalArgumentException if n < 1. Must run in O(n log n) time <br>
	 * <br>
	 * <strong>Note:</strong> For random number generation, use the
	 * RandomSingleton class from Project 1; this generator might be modified
	 * slightly for use in this project. To generate a random permutation of 1
	 * through n, use the <a href=
	 * "http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm"
	 * >"shuffle" algorithm</a>
	 * <br>
	 * <br>
	 * Runs in <strong>O(n log n)</strong> time.
	 * 
	 * @param n
	 *            Number of random rankings to create
	 * @throws IllegalArgumentException
	 *             if n < 1
	 */
	public Ranking(int n) 
	{
		if (n<1)
			throw new IllegalArgumentException();
		
		
		
		Integer[] items = new Integer[n];
		for (int i = 0; i < n; ++i) items[i] = i+1; // O(n)
		
		Random rand = RandomSingleton.getInstance();
		
		// this shuffles the elements
		int j;		
		for (int i = n-1; i>=1; --i) // O(n)
		{
			j = rand.nextInt(i+1);
			int temp = (int) items[j];
			items[j] = items[i];
			items[i] = temp;
		}
		
		ranks = new HashMap<Integer,Integer>();
		ranksOpposite = new HashMap<Integer,Integer>();
		j = 1;
		for (Integer item : items) // O(n)
		{
			ranksOpposite.put(item, j);
			ranks.put(j++, item);
		}
			
		Integer[] newRank = new Integer[items.length];
		for (int i = 0; i < items.length; ++i) newRank[i] = items[i]; // O(n)
		
		Map.Entry<Integer[], Integer> pair = sortAndCount(newRank); // O(n log n)
		inversionCount = pair.getValue();
	}

	/**
	 * Constructs a ranking o of the set U = {1,...,rank.length}, where o(i) =
	 * rank[i-1]. Throws a NullPointerException if rank is null. Throws an
	 * IllegalArgumentException if rank does not consist of distinct elements
	 * between 1 and rank.length. Must run in O(n log n) time or better, where n
	 * = rank.length. 
	 * <br>
	 * <br>
	 * Runs in <strong>O(n log n)</strong> time.
	 * 
	 * @param rank
	 *            Ranking set
	 * @throws NullPointerException
	 *             if rank is null
	 * @throws IllegalArgumentException
	 *             if rank does not consist of distinct elements between 1 and
	 *             rank.length
	 */
	public Ranking(int[] rank) 
	{
		if (rank==null)
			throw new NullPointerException();
		if(rank.length==0)
			throw new IllegalArgumentException();
		
		int[] rankTemp = Arrays.copyOf(rank, rank.length);
		Arrays.sort(rankTemp); // roughly (n log n)
		
		// checks to see if array will produce a valid ranking
		for (int i = 0; i < rankTemp.length; ++i) // O(n)
		{
			if (rankTemp[i] != i+1)
				throw new IllegalArgumentException();
		}

			ranks = new HashMap<Integer,Integer>();
			ranksOpposite = new HashMap<Integer,Integer>();
			int j = 1;
			for (int i = 0; i < rank.length; ++i) // O(n)
			{
				ranksOpposite.put(rank[i], j);
				ranks.put(j++, rank[i]);
			}
					
			Integer[] newRank = new Integer[rank.length];
			int i = 0;
			for (int value : rank) // O(n)
			{
				newRank[i++] = Integer.valueOf(value);
			}
			
			Map.Entry<Integer[], Integer> pair = sortAndCount(newRank); // sort runs in O(n log n)
			
			inversionCount = pair.getValue();
	}

	/**
	 * Constructs a ranking of the set U = {1,...,scores.length}, where element
	 * i gets rank k if and only if scores[i-1] is the kth largest element in
	 * the array scores. Throws a NullPointerException if scores is null. Throws
	 * an IllegalArgumentException if scores contains duplicate values. Must run
	 * in O(n log n) time, where n = scores.length. <br>
	 * <br>
	 * Example: <br>
	 * Suppose scores = (0.75, 0.36, 0.65, -1.5, 0.85). Then, the corresponding
	 * ranking is o = (2, 4, 3, 5, 1).
	 * 
	 * <br>
	 * <br>
	 * Runs in <strong>O(n log n)</strong> time.
	 * 
	 * 
	 * @param scores
	 *            Scores set
	 * @throws NullPointerException
	 *             if scores is null
	 * @throws IllegalArgumentException
	 *             if scores contains duplicate values
	 */
	public Ranking(float[] scores) 
	{
		if(scores==null)
			throw new NullPointerException();
		if (scores.length==0)
			throw new IllegalArgumentException();
		
		
		ranks = new HashMap<Integer,Integer>();
		ranksOpposite = new HashMap<Integer,Integer>();
		HashMap<Object,Integer> sortedranks = new HashMap<Object,Integer>();

		
		float[] tempScores = Arrays.copyOf(scores, scores.length);
		Arrays.sort(tempScores); // O(n log n)
		
		
		int j = 5;
		for (int i = tempScores.length-1; i >= 0; --i) sortedranks.put(tempScores[i], j--);
		
		for (int i = 0; i < scores.length; ++i) 
		{
			ranks.put(i+1, sortedranks.get(scores[i]));
			ranksOpposite.put(sortedranks.get(scores[i]), i+1);
			
		}

		// HashMap automatically removes duplicate keys, so these will be different right away
		if (sortedranks.size() != scores.length)
			throw new IllegalArgumentException();
		
		Integer[] rankArr = new Integer[ranks.size()];
		int i = 0;
		for (Map.Entry<Integer, Integer> entry : ranks.entrySet()) rankArr[i++] = entry.getValue();
		
		Map.Entry<Integer[], Integer> pair = sortAndCount(rankArr); // O(n log n)
		
		inversionCount = pair.getValue();
	}


	/**
	 * @return the number of items in the ranking. Must run in O(1) time
	 */
	public int getNumItems() 
	{
		return ranks.size();
	}

	/**
	 * Returns the rank of item i. Throws an IllegalArgumentException if item i
	 * is not present in the ranking. Must run in O(1) time.
	 * 
	 * @param i
	 *            Item to get rank for
	 * @return the rank of item i
	 * @throws IllegalArgumentException
	 *             if item i is not present in the ranking
	 */
	public int getRank(int i) 
	{
		// check for negative and greater than n
		if (i<1 || i>ranks.size())
			throw new IllegalArgumentException();
		
		Integer item = ranks.get(i); // O(1) average case. O(n) worst case, but not likely
		if (item==null)
			throw new IllegalArgumentException();
		
		return item.intValue();
	}

	/**
	 * Returns the footrule distance between r1 and r2. Throws a
	 * NullPointerException if either r1 or r2 is null. Throws an
	 * IllegalArgumentException if r1 and r2 have different lengths. Must run in
	 * O(n) time, where n is the number of elements in r1 (or r2).
	 * 
	 * @param r1
	 *            Ranking object
	 * @param r2
	 *            Ranking object
	 * @return the footrule distance between r1 and r2
	 * @throws NullPointerException
	 *             if either r1 or r2 is null
	 * @throws IllegalArgumentException
	 *             if r1 and r2 have different lengths
	 */
	public static int footrule(Ranking r1, Ranking r2) 
	{
		if(r1==null || r2==null)
			throw new NullPointerException();
		if (r1.getNumItems() != r2.getNumItems())
			throw new IllegalArgumentException();
		
		int total = 0;
		for (int i = 1; i <= r1.getNumItems(); ++i) // O(n)
		{
			total += Math.abs((Integer) r1.getRankHM().get(i) - (Integer) r2.getRankHM().get(i));
		}
		
		return total;
	}

	/**
	 * Returns the Kemeny distance between r1 and r2. Throws a
	 * NullPointerException if either r1 or r2 is null. Throws an
	 * IllegalArgumentException if r1 and r2 have different lengths. Must run in
	 * O(n log n) time, where n is the number of elements in r1 (or r2).
	 * 
	 * @param r1
	 *            Ranking object
	 * @param r2
	 *            Ranking object
	 * @return the Kemeny distance between r1 and r2
	 * @throws NullPointerException
	 *             if either r1 or r2 is null
	 * @throws IllegalArgumentException
	 *             if r1 and r2 have different lengths
	 */
	public static int kemeny(Ranking r1, Ranking r2) 
	{
		if (r1==null || r2==null)
			throw new NullPointerException();
		if (r1.getNumItems() != r2.getNumItems())
			throw new IllegalArgumentException();
		
		ArrayList<Integer> valueSet = new ArrayList<Integer>();
		Integer[] compRank = new Integer[r1.getNumItems()];
		
		int idx = 0;
		for (int i = 1; i <= r1.getRankHM().size(); ++i) valueSet.add(r1.getRanksOppHM().get(i)); // O(n)
		
		idx = 0;
		for (Integer i : valueSet) compRank[idx++] = r2.getRank(i); // O(n)
		
		Map.Entry<Integer[], Integer> pair = sortAndCount(compRank); // O(n log n)
				
		return pair.getValue();
	}

	/**
	 * Returns the footrule distance between this and other. Throws a
	 * NullPointerException if other is null. Throws an IllegalArgumentException
	 * if this and other have different lengths. Must run in O(n) time, where n
	 * is the number of elements in this (or other).
	 * 
	 * @param other
	 *            Ranking object
	 * @return the footrule distance between this and other
	 * @throws NullPointerException
	 *             if other is null
	 * @throws IllegalArgumentException
	 *             if this and other have different lengths
	 */
	public int fDist(Ranking other) 
	{
		if (other==null)
			throw new NullPointerException();
		if (this.getNumItems() != other.getNumItems())
			throw new IllegalArgumentException();
		
		int total = 0;
		for (int i = 1; i <= other.getNumItems(); ++i) // O(n)
		{
			total += Math.abs((Integer) ranks.get(i) - (Integer) other.getRankHM().get(i));
		}

		return total;
	}

	/**
	 * Returns the Kemeny distance between this and other. Throws a
	 * NullPointerException if other is null. Throws an IllegalArgumentException
	 * if this and other have different lengths. Must run in O(n log n) time,
	 * where n is the number of elements in this (or other).
	 * 
	 * @param other
	 *            Ranking object
	 * @return the Kemeny distance between this and other
	 * @throws NullPointerException
	 *             if other is null
	 * @throws IllegalArgumentException
	 *             if this and other have different lengths
	 */
	public int kDist(Ranking other) 
	{
		if (other==null)
			throw new NullPointerException();
		if (this.getNumItems() != other.getNumItems())
			throw new IllegalArgumentException();
		
		ArrayList<Integer> valueSet = new ArrayList<Integer>();
		Integer[] compRank = new Integer[other.getNumItems()];
		
		int idx = 0;
		for (int i = 1; i <= ranks.size(); ++i) valueSet.add(ranksOpposite.get(i)); // O(n)
		
		idx = 0;
		for (Integer i : valueSet) compRank[idx++] = other.getRank(i); // O(n)

		Map.Entry<Integer[], Integer> pair = sortAndCount(compRank); // O(n log n)
		
		return pair.getValue();
	}

	/**
	 * Returns the number of inversions in this ranking. Should run in O(n log
	 * n) time, where n is the number of elements in this. <br>
	 * <br>
	 * <strong>Note:</strong> Since Ranking objects are immutable, you could, in
	 * fact, compute the number of inversions in a ranking just once, at the
	 * time of creation, and store it for later access. With this
	 * implementation, invCount would take O(1) time. You are free to implement
	 * this version or the one that computes inversions every time the method is
	 * called; your documentation should indicate clearly which approach your
	 * method uses.<br>
	 * <br>
	 * <br>
	 * In my implementation, this method runs in <strong>O(1)</strong> time, because 
	 * the number of inversions is counted in the constructor and saved to an instance variable
	 * 
	 * 
	 * @return the number of inversions in t
	 */
	public int invCount() 
	{
		return inversionCount; // O(1)
	}

	

	/**
	 *  Sorts and counts finds the number of inversions in a given array
	 * @param arr
	 * - The array to be sorted and and counted for inversions
	 * @return
	 * - A pair containing the sorted array and the number of inversions
	 */
	private static Map.Entry<Integer[], Integer> sortAndCount(Integer[] arr)
	{
		if (arr.length==1)
			return new AbstractMap.SimpleEntry<Integer[], Integer>(arr, 0);
		
		int m = (arr.length)/2;
		Integer[] left = Arrays.copyOfRange(arr, 0, m);
		Integer[] right = Arrays.copyOfRange(arr, m, arr.length);
		
		Map.Entry<Integer[], Integer> leftInv = sortAndCount(left);
		Map.Entry<Integer[], Integer> rightInv = sortAndCount(right);
		
		Map.Entry<Integer[], Integer> pair = mergeAndCount(leftInv.getKey(), rightInv.getKey());
		Integer invCross = leftInv.getValue() + rightInv.getValue() + pair.getValue(); 
		Map.Entry<Integer[], Integer> finalPair = new AbstractMap.SimpleEntry<Integer[], Integer>(pair.getKey(), invCross);
		return finalPair;
	}
	
	/**
	 * Merge and count performs the merge step in the sort and count algorithm
	 * 
	 * @param left
	 * - A sorted array of distinct elements
	 * @param right
	 *- A sorted array of distinct elements
	 * @return
	 * - A pair containing the sorted combined array and the number of inversions
	 */
	private static Map.Entry<Integer[], Integer> mergeAndCount(Integer[] left, Integer[] right)
	{
		int i = 0;
		int j = 0;
		int count = 0;
		int p = left.length;
		int q = right.length;
		ArrayList<Integer> gamma = new ArrayList<Integer>();
		
		
		while (i < p && j < q)
		{
			if (left[i] < right[j])
			{
				gamma.add(left[i]);

				i++;
			}
			else if (right[j] < left[i])
			{
				gamma.add(right[j]);
				
				count = count + (p -(i+1)+1);
				j++;
			}
		}
		if ((i+1) > p)
		{
			for (int idx = j; idx < q; ++idx)
			{
				gamma.add(right[idx]);
			}
		}
		if ((j+1) > q)
		{
			for (int idx = i; idx < p; ++idx)
			{
				gamma.add(left[idx]);
			}
		}
		Integer[] ret = new Integer[gamma.size()];
		ret = gamma.toArray(ret);
		return new AbstractMap.SimpleEntry<Integer[], Integer>(ret, count);
		
	}
	

	/**
	 * This is only used for the static methods kemeny and footrule
	 *  
	 * @return
	 * - This returns the HashMap that represents the ranking of the Ranking class.<br>
	 * - Not available outside of the Ranking implementation.
	 */
	private HashMap<Integer, Integer> getRankHM()
	{
		return ranks;
	}

	/**
	 * This is only used for the static methods kemeny and footrule
	 * 
	 * @return
	 * - This returns the HashMap that represents the an inverse of the current Ranking. <br>
	 * - Not available outside of the Ranking implementation.
	 */
	private HashMap<Integer, Integer> getRanksOppHM()
	{
		return ranksOpposite;
	}
	

}
